3.9 KB · ⇊ 3 parts · ⤓ Micron 3.9 KB · ⤓ HTML 21.6 KB

top

The r-to-1 collision problem is an important theoretical problem in complexity theory, quantum computing, and computational mathematics. The collision problem most often refers to the 2-to-1 versioncite-ref-1[1]: given n {\displaystyle n} even and a function f : { 1 , … … , n } → → { 1 , … … , n } {\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}} , we are promised that f is either 1-to-1 or 2-to-1. We are only allowed to make queries about the value of f ( i ) {\displaystyle f(i)} for any i ∈ ∈ { 1 , … … , n } {\displaystyle i\in \{1,\ldots ,n\}} . The problem then asks how many such queries we need to make to determine with certainty whether f is 1-to-1 or 2-to-1.

• Classical solutions

• Deterministic

• Randomized

• Quantum solution

• References

Solving the 2-to-1 version deterministically requires n 2 + 1 {\textstyle {\frac {n}{2}}+1} queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires n r + 1 {\textstyle {\frac {n}{r}}+1} queries.

This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after n r + 1 {\textstyle {\frac {n}{r}}+1} queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus, n r + 1 {\textstyle {\frac {n}{r}}+1} queries suffice. If we are unlucky, then the first n / r {\displaystyle n/r} queries could return distinct answers, so n r + 1 {\textstyle {\frac {n}{r}}+1} queries is also necessary.

If we allow randomness, the problem is easier. By the birthday paradox, if we choose (distinct) queries at random, then with high probability we find a collision in any fixed 2-to-1 function after Θ Θ ( n ) {\displaystyle \Theta ({\sqrt {n}})} queries.

The BHT algorithm, which uses Grover's algorithm, solves this problem optimally by only making O ( n 1 / 3 ) {\displaystyle O(n^{1/3})} queries to f. The matching lower bound of Ω Ω ( n 1 / 3 ) {\displaystyle \Omega (n^{1/3})} was proved by Aaronson and Shi using the polynomial methodcite-ref-2[2].

cite-note-11. ↑ citerefscott-aaronson2004Scott Aaronson (2004). "Limits on Efficient Computation in the Physical World" (PDF).

cite-note-22. ↑ citerefscott-aaronson-and-yaoyun-shi2004Scott Aaronson and Yaoyun Shi (2004). "Quantum lower bounds for the collision and the element distinctness problems".